「Luogu P2523」[HAOI2011]Problem c 解题报告

题面

解题思路

动态规划

分析

显然，如果我们对每个确定的位置进行标记，然后做一个后缀和，就可以得出无解的情况，得出 $i$ 位置后最多能放元素的个数

显然，如果我们对这个后缀和从前往后取个 $min$ 的话，我们就可以真正意义上的出 $i$ 位置后最多能放的元素个数（然而这并没有什么软用

实际有用的就是怎么去计算方案

显然直接暴上组合数是会炸的（无法计算重复的部分），那么我们就 $DP$

转移方程为：

$$\large f_{i,j}=\sum_{k=0}^{s_i}\binom{j}{k}f_{i+1,j-k} \pmod p$$

$f_{i,j}$ 表示倒序做到 $i$ 这个位置，安排了 $j$ 个人的方案数，$\large \binom{j}{k}$ 表示从这 $j$ 个人中选出 $k$ 个，安排在 $i$ 这个位置的方案，转移即可

就做完了

Warning

1、记得开 long long

2、累加

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 303
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,m,p,T;
int s[N],f[N][N],C[N][N];
inline int dec(rint x) {return (x>=p)?x-p:x;}
int main() {
    rint i,j,k;T=read();
    while(T--) {n=read(),m=read(),p=read();
        memset(s,0,sizeof(s)),
        memset(f,0,sizeof(f));
        for(i=1;i<=m;i++) read(),++s[read()];
        for(i=n;i;--i)
            if((s[i]+=s[i+1])>n-i+1) break;
        if(i) printf("NO\n");
        else {m=n-m,C[0][0]=1;
            for(i=1;i<=m;i++) {
                C[i][0]=1;
                for(j=1;j<=i;j++)
                    C[i][j]=dec(C[i-1][j-1]+C[i-1][j]);
            }s[0]=inf;
            for(i=1;i<=n;++i) s[i]=min(s[i-1],n-i+1-s[i]);//求最多的个数，没什么用
            f[n+1][0]=1;//记得初始值
            for(i=n;i;i--) {
                for(j=0;j<=s[i];++j) {
                    for(k=0;k<=j;k++)
                        f[i][j]=dec(f[i][j]+(LL)C[j][k]*f[i+1][j-k]%p);//转移就完了
                }
            }printf("YES %d\n",f[1][m]);
        }
    }
    return 0;
}